package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: xiaomi
 * @date: 2021/3/28
 * @description: 剑指 Offer 47. 礼物的最大价值
 * https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
 */
public class B_剑指Offer47_礼物的最大价值 {

    public static void main(String[] args) {

    }

    /**
     * dp[i][j](i行j列) 代表落子到 i,j 处，剩余能拿到的最大礼物总值
     *
     * @param grid
     * @return
     */
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int mEndIndex = m - 1;
        int nEndIndex = n - 1;
        int[][] dp = new int[m][n];
        dp[mEndIndex][nEndIndex] = 0;
        for (int i = nEndIndex - 1; i >= 0; i--) {
            //最末行
            dp[mEndIndex][i] = dp[mEndIndex][i + 1] + grid[mEndIndex][i + 1];
        }
        for (int i = mEndIndex - 1; i >= 0; i--) {
            //最末列
            dp[i][nEndIndex] = dp[i + 1][nEndIndex] + grid[i + 1][nEndIndex];
        }
        for (int i = mEndIndex - 1; i >= 0; i--) {
            for (int j = nEndIndex - 1; j >= 0; j--) {
                dp[i][j] = Math.max(dp[i][j + 1] + grid[i][j + 1], dp[i + 1][j] + grid[i + 1][j]);
            }
        }
        return dp[0][0];
    }
}
